/* 设计算法，求无向连通图距顶点v最远的一个结点（即路径长度最大） */

#include <iostream>
#include "algraph.h"
using namespace std;

// 广度优先搜索 -- 返回最后一个被访问的结点序号
int BFS(ALGraph *G, int v)
{
  ArcNode *p;
  
  // 创建队列
  int j, que[maxsize];
  int front = 0, rear = 0;
  
  // 访问标记
  int visit[maxsize];
  
  // 初始时，均未被访问
  for (int i = 0; i < G->numver; ++i)
    visit[i] = 0;
  
  // 头节点进队
  que[++rear] = v;
  
  // 更新访问记录
  visit[v] = 1;
  
  // 如果队列不为空
  while (front != rear)
  {
    // 结点出队
    j = que[++front];
    
    // 访问其邻接结点
    p = G->adjlist[j].firstarc;
    
    // 邻接结点存在
    while (p != NULL)
    {
      // 邻接结点未被访问
      if (visit[p->adjvex] == 0)
      {
        // 更新访问记录
        visit[p->adjvex] = 1;
        
        // 进队
        que[++rear] = p->adjvex;
      }
      
      // 到下一个邻接结点
      p = p->nextarc;
    }
  }
  
  // 返回最后一个被访问的元素
  return j;
}

int main()
{
  // 创建图 -- 邻接表
  ALGraph *G = create_algraph(4, 4);
  
  // 求距离最远的结点序号
  cout << BFS(G, 0);
  return 0;
}